package com.xy6.algo.search;


/**
 * 二分查找
 * <p>时间复杂度：O(log2^n)
 * <p>适用于有序的、静态集合
 * 
 * <pre>
 * 取集合中间元素，与目标值比较，如果中间元素与目标值相等，则返回。
 * 如果中间元素比目标值大，则将集合缩小为[首元素，中间元素前一个元素]。
 * 如果中间元素比目标值小，则将集合缩小为[中间元素下一个元素，尾元素]。
 * 取集合中间元素，与目标值比较，如果中间元素与目标值相等，则返回。
 * 递归进行，直到集合元素为1，未找到匹配值，返回。
 * </pre>
 * 
 * @author zhang
 * @since 2017-08-03
 */
public class SearchBinary {

	public static void main(String[] args) {
		int[] arr = new int[] { 1, 2, 3, 5 };
		int index = search(arr, 3);
		System.out.println(index);
	}

	public static int search(int[] arr, int val) {
		int index = -1;
		int min = 0;
		int max = arr.length - 1;
		while (min <= max) {
			if (arr[min] == val) {
				index = min;
				break;
			}
			if (arr[max] == val) {
				index = max;
				break;
			}
			
			int mid = (min + max) / 2;
			if (arr[mid] < val) {
				min = mid + 1;
			} else if (arr[mid] == val) {
				index = mid;
				break;
			} else {
				max = mid - 1;
			}
		}
		return index;
	}

}
